1. Field
The present systems, devices and methods generally relate to superconducting computing, for example analog or quantum computing employing processors that operate at superconducting temperatures.
2. Description of the Related Art
A Turing machine is a theoretical computing system, described in 1936 by Alan Turing. A Turing machine that can efficiently simulate any other Turing machine is called a Universal Turing Machine (UTM). The Church-Turing thesis states that any practical computing model has either the equivalent or a subset of the capabilities of a UTM.
A quantum computer is any physical system that harnesses one or more quantum effects to perform a computation. A quantum computer that can efficiently simulate any other quantum computer is called a Universal Quantum Computer (UQC).
In 1981 Richard P. Feynman proposed that quantum computers could be used to solve certain computational problems more efficiently than a UTM and therefore invalidate the Church-Turing thesis. See e.g., Feynman R. P., “Simulating Physics with Computers”, International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. For example, Feynman noted that a quantum computer could be used to simulate certain other quantum systems, allowing exponentially faster calculation of certain properties of the simulated quantum system than is possible using a UTM.
Approaches to Quantum Computation
There are several general approaches to the design and operation of quantum computers. One such approach is the “circuit model” of quantum computation. In this approach, qubits are acted upon by sequences of logical gates that are the compiled representation of an algorithm. Circuit model quantum computers have several serious barriers to practical implementation. In the circuit model, it is required that qubits remain coherent over time periods much longer than the single-gate time. This requirement arises because circuit model quantum computers require operations that are collectively called quantum error correction in order to operate. Quantum error correction cannot be performed without the circuit model quantum computer's qubits being capable of maintaining quantum coherence over time periods on the order of 1,000 times the single-gate time. Much research has been focused on developing qubits with coherence sufficient to form the basic information units of circuit model quantum computers. See e.g., Shor, P. W. “Introduction to Quantum Algorithms”, arXiv.org:quant-ph/0005003 (2001), pp. 1-27. The art is still hampered by an inability to increase the coherence of qubits to acceptable levels for designing and operating practical circuit model quantum computers.
Another approach to quantum computation, involves using the natural physical evolution of a system of coupled quantum systems as a computational system. This approach does not make critical use of quantum gates and circuits. Instead, starting from a known initial Hamiltonian, it relies upon the guided physical evolution of a system of coupled quantum systems wherein the problem to be solved has been encoded in the terms of the system's Hamiltonian, so that the final state of the system of coupled quantum systems contains information relating to the answer to the problem to be solved. This approach does not require long qubit coherence times. Examples of this type of approach include adiabatic quantum computation, cluster-state quantum computation, one-way quantum computation, quantum annealing and classical annealing, and are described, for example, in Farhi et al., “Quantum Adiabatic Evolution Algorithms versus Simulated Annealing” arXiv.org:quant-ph/0201031 (2002), pp 1-24.
Qubits
As mentioned previously, qubits can be used as fundamental units of information for a quantum computer. As with bits in UTMs, qubits can refer to at least two distinct quantities; a qubit can refer to the actual physical device in which information is stored, and it can also refer to the unit of information itself, abstracted away from its physical device.
Qubits generalize the concept of a classical digital bit. A classical information storage device can encode two discrete states, typically labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the classical information storage device, such as direction or magnitude of magnetic field, current, or voltage, where the quantity encoding the bit state behaves according to the laws of classical physics. A qubit also contains two discrete physical states, which can also be labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the quantum information storage device, such as direction or magnitude of magnetic field, current, or voltage, where the quantity encoding the bit state behaves according to the laws of quantum physics. If the physical quantity that stores these states behaves quantum mechanically, the device can additionally be placed in a superposition of 0 and 1. That is, the qubit can exist in both a “0” and “1” state at the same time, and so can perform a computation on both states simultaneously. In general, N qubits can be in a superposition of 2N states. Quantum algorithms make use of the superposition property to speed up some computations.
In standard notation, the basis states of a qubit are referred to as the |0 and |1  states. During quantum computation, the state of a qubit, in general, is a superposition of basis states so that the qubit has a nonzero probability of occupying the |0  basis state and a simultaneous nonzero probability of occupying the |1  basis state. Mathematically, a superposition of basis states means that the overall state of the qubit, which is denoted |Ψ, has the form |Ψ=a|0 +b|1 , where a and b are coefficients corresponding to the probabilities |a|2 and |b|2, respectively. The coefficients a and b each have real and imaginary components, which allows the phase of the qubit to be characterized. The quantum nature of a qubit is largely derived from its ability to exist in a coherent superposition of basis states and for the state of the qubit to have a phase. A qubit will retain this ability to exist as a coherent superposition of basis states when the qubit is sufficiently isolated from sources of decoherence.
To complete a computation using a qubit, the state of the qubit is measured (i.e., read out). Typically, when a measurement of the qubit is performed, the quantum nature of the qubit is temporarily lost and the superposition of basis states collapses to either the |0 basis state or the |1 basis state and thus regaining its similarity to a conventional bit. The actual state of the qubit after it has collapsed depends on the probabilities |a|2 and |b|2 immediately prior to the readout operation.
Superconducting Qubits
There are many different hardware and software approaches under consideration for use in quantum computers. One hardware approach uses integrated circuits formed of superconducting materials, such as aluminum or niobium. The technologies and processes involved in designing and fabricating superconducting integrated circuits are similar to those used for conventional integrated circuits.
Superconducting qubits are a type of superconducting device that can be included in a superconducting integrated circuit. Superconducting qubits can be separated into several categories depending on the physical property used to encode information. For example, they may be separated into charge, flux and phase devices, as discussed in, for example Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400. Charge devices store and manipulate information in the charge states of the device, where elementary charges consist of pairs of electrons called Cooper pairs. A Cooper pair has a charge of 2e and consists of two electrons bound together by, for example, a phonon interaction. See e.g., Nielsen and Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000), pp. 343-345. Flux devices store information in a variable related to the magnetic flux through some part of the device. Phase devices store information in a variable related to the difference in superconducting phase between two regions of the phase device. Recently, hybrid devices using two or more of charge, flux and phase degrees of freedom have been developed. See e.g., U.S. Pat. No. 6,838,694 and U.S. Pat. No. 7,335,909.
Computational Complexity Theory
In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given computational problem. This cost is usually measured in terms of abstract parameters such as time and space, called computational resources. Time represents the number of steps required to solve a problem and space represents the quantity of information storage required or how much memory is required.
Computational complexity theory classifies computational problems into complexity classes. The number of complexity classes is ever changing, as new ones are defined and existing ones merge through the contributions of computer scientists. The complexity classes of decision problems include:
1. P—The complexity class containing decision problems that can be solved by a deterministic UTM using a polynomial amount of computation time;
2. NP (“Non-deterministic Polynomial time”)—The set of decision problems solvable in polynomial time on a non-deterministic UTM. Equivalently, it is the set of problems that can be “verified” by a deterministic UTM in polynomial time;
3. NP-hard (Nondeterministic Polynomial-time hard)—A problem H is in the class NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H. That is to say, L can be solved in polynomial time by an oracle machine with an oracle for H;
4. NP-complete—A decision problem C is NP-complete if it is complete for NP, meaning that:
(a) it is in NP and
(b) it is NP-hard,
i.e., every other problem in NP is reducible to it. “Reducible” means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms instances I ε L into instances c ε C, such that the answer to c is YES if and only if the answer to I is YES. To prove that an NP problem A is in fact an NP-complete problem it is sufficient to show that an already known NP-complete problem reduces to A.
Decision problems have binary outcomes. Problems in NP are computation problems for which there exists a polynomial time verification. That is, it takes no more than polynomial time (class P) in the size of the problem to verify a potential solution. It may take more than polynomial time, however, to find a potential solution. NP-hard problems are at least as hard as any problem in NP.
Optimization problems are problems for which one or more objective functions are minimized or maximized over a set of variables, sometimes subject to a set of constraints. For example, the Traveling Salesman Problem (“TSP”) is an optimization problem where an objective function representing, for example, distance or cost, must be optimized to find an itinerary, which is encoded in a set of variables representing the optimized solution to the problem. For example, given a list of locations, the problem may consist of finding the shortest route that visits all locations exactly once. Other examples of optimization problems include Maximum Independent Set, integer programming, constraint optimization, factoring, prediction modeling, and k-SAT. These problems are abstractions of many real-world optimization problems, such as operations research, financial portfolio selection, scheduling, supply management, circuit design, and travel route optimization. Many large-scale decision-based optimization problems are NP-hard. See e.g., “A High-Level Look at Optimization: Past, Present, and Future” e-Optimization.com, 2000.
Simulation problems typically deal with the simulation of one system by another system, usually over a period of time. For example, computer simulations can be made of business processes, ecological habitats, protein folding, molecular ground states, quantum systems, and the like. Such problems often include many different entities with complex inter-relationships and behavioral rules. In Feynman it was suggested that a quantum system could be used to simulate some physical systems more efficiently than a UTM.
Many optimization and simulation problems are not solvable using UTMs. Because of this limitation, there is need in the art for computational devices capable of solving computational problems beyond the scope of UTMs. In the field of protein folding, for example, grid computing systems and supercomputers have been used to try to simulate large protein systems. See Shirts et al., 2000, Science 290, pp. 1903-1904, and Allen et al., 2001, IBM Systems Journal 40, p. 310. The NEOS solver is an online network solver for optimization problems, where a user submits an optimization problem, selects an algorithm to solve it, and then a central server directs the problem to a computer in the network capable of running the selected algorithm. See e.g., Dolan et al., 2002, SIAM News Vol. 35, p. 6. Other digital computer-based systems and methods for solving optimization problems can be found, for example, in Fourer et al., 2001, Interfaces 31, pp. 130-150. All these methods are limited, however, by the fact they utilize digital computers, which are UTMs, and accordingly, are subject to the limits of classical computing that impose unfavorable scaling between problem size and solution time.
Persistent Current ZZ Coupler
In FIG. 1 shows schematic diagram of a controllable ZZ coupler 100. Coupler 100 includes a loop 101 of superconducting material interrupted by a single Josephson junction 102 and is used to couple a first qubit 110 and a second qubit 120. Qubit 110 includes a loop 111 of superconducting material interrupted by a compound Josephson junction 112 and is coupled to coupler 100 through the exchange of flux 103 between coupler 100 and qubit 110. Loop 111 is threaded by flux 115 created by electrical current flowing through a magnetic flux inductor 116. Flux 115 controls the energy bias of qubit 110. Compound Josephson junction 112 is threaded by flux 113 created by electrical current flowing through magnetic flux inductor 114. Flux 113 controls the transverse term Δ1 of qubit 110. Qubit 120 includes a loop 121 of superconducting material interrupted by a compound Josephson junction 122 and is coupled to coupler 100 through the exchange of flux 104 between coupler 100 and qubit 120. The loop 121 is threaded by flux 125 created by electrical current flowing through magnetic flux inductor 126. Flux 125 controls the energy bias of qubit 120. Compound Josephson junction 122 is threaded by flux 123 created by electrical current flowing through magnetic flux inductor 124. Flux 123 controls the transverse term Δ2of qubit 120. Loop 101 is threaded by flux 105 created by electrical current flowing through magnetic flux inductor 106.
Flux 105 produced by magnetic flux inductor 106 threads loop 101 and controls the state of coupler 100. Coupler 100 is capable of producing a zero coupling between qubit 110 and qubit 120, an anti-ferromagnetic coupling between qubit 110 and qubit 120, and a ferromagnetic coupling between qubit 110 and qubit 120.
It may be desirable to weaken non-adiabatic couplings produced by coupler 100 so that adiabatic couplings (e.g., σz1σz2 interactions such as anti-ferromagnetic coupling between qubit 110 and qubit 120 and ferromagnetic coupling between qubit 110 and qubit 120) dominate. For further discussion of adiabatic couplings, see e.g., Hutter et al., arXiv:cond-mat/0602086 (2006).
The Hamiltonians which coupler 100 is capable of embedding allow for diagonalized ZZ coupling interactions (e.g., σz1σz2 interactions) and do not allow for the production of off-diagonal YY couplings (σy1σy2 interactions). The Hamiltonian H for coupler 100 is:
      H    =                            ∑                                    i              =              1                        ,            2                          ⁢                              h            i                    ⁢                      σ            z            i                              +                        J                      1            ,            2                    ZZ                ⁢                  σ          z          1                ⁢                  σ          z          2                      ,where 1 and 2 represent qubit 110 and qubit 120 respectively, h1 is the energy bias of qubit 110 and is controllable by adjusting the amount of flux 115 threading loop 111, h2 is the energy bias of qubit 120 and is controllable by adjusting the amount of flux 125 threading loop 121, σz1 is the z-Pauli matrix of qubit 110, σz2 is the z-Pauli matrix of qubit 120, and J1,2ZZ is the diagonal coupling coefficient between qubit 110 and qubit 120 and is controllable by adjusting the amount of flux 105 threading loop 101. The parameters Δ1 and Δ2 are the flux tunneling amplitude terms of qubit 110 and qubit 120 respectively. The transverse terms, Δ1 and Δ2, are respectively controllable by adjusting the amount of flux 113 threading compound Josephson junction 112 and the amount of flux 123 threading compound Josephson junction 122. Δ1 and Δ2 are suppressed during the operation of coupler 100 and effectively have a value of zero and may be ignored within the Hamiltonian H of coupler 100.
For further discussion of coupler 100, see e.g., Harris et al., “Sign-and Magnitude-Tunable Coupler for Superconducting Flux Qubits”, Physical Review Letters 98 (2007) 177001, and van der Brink et al., “Mediated tunable coupling of flux qubits,” New Journal of Physics 7 (2005) 230.
Zero-Persistent Current ZZ Coupler
FIG. 2 is a schematic diagram of controllable ZZ coupler 200 is used to inductively couple a first qubit 210 and a second qubit 220. The coupler 200 is comprised of a loop 201 of superconducting material interrupted by compound Josephson junction 202. Qubit 210 is comprised of a loop 211 of superconducting material interrupted by compound Josephson junction 212 and is coupled to coupler 200 through the exchange of flux 203 between coupler 200 and qubit 210. Loop 211 is threaded by flux 215 created by electrical current flowing through a magnetic flux inductor 216. Flux 215 controls the energy bias of qubit 210. Compound Josephson junction 212 is threaded by flux 213 created by electrical current flowing through a magnetic flux inductor 214. Flux 213 controls the transverse term Δ1 of qubit 210. Qubit 220 is comprised of a loop 221 of superconducting material interrupted by a compound Josephson junction 222 and is coupled to coupler 200 through the exchange of flux 204 between coupler 200 and qubit 220. Loop 221 is threaded by flux 225 created by electrical current flowing through a magnetic flux inductor 226. Flux 225 controls the energy bias of qubit 220. Compound Josephson junction 222 is threaded by flux 223 created by electrical current flowing through a magnetic flux inductor 224. Flux 223 controls the transverse term Δ2 of qubit 220. Compound Josephson junction 202 is threaded by flux 205 created by current flowing through a magnetic flux inductor 206. Flux 205 produced by magnetic flux inductor 206 threads compound Josephson junction 202 of coupler 200 and controls the state of coupler 200.
Coupler 200 is capable of producing a zero coupling between qubit 210 and qubit 220. To produce the zero coupling between qubit 210 and qubit 220, the amount of flux 205 threading compound Josephson junction 202 is adjusted to be about (n+½)φ0, wherein n is an integer. Coupler 200 is capable of producing an anti-ferromagnetic coupling between qubit 210 and qubit 220. To produce such a coupling between qubit 210 and qubit 220, the amount of flux 205 threading compound Josephson junction 202 is adjusted to be about (2n)φ0, wherein n is an integer. Coupler 200 is capable of producing a ferromagnetic coupling between qubit 210 and qubit 220. To produce such a coupling between qubit 210 and qubit 220, the amount of flux 205 threading compound Josephson junction 202 is adjusted to be about (2n+1)φ0, wherein n is an integer. An amount of flux (not shown in FIG. 2) threading the loop 201 can be applied to render the net value of flux threading the loop 201 to be about zero. Where the net value of flux threading the loop 201 is about zero a minimum amount of persistent current will be present within the loop 201 during states produced by coupler 200.
It may be desirable to weaken non-adiabatic couplings produced by coupler 200 so that adiabatic couplings (e.g., σz1σz2 interactions such as anti-ferromagnetic coupling between qubit 210 and qubit 220 and ferromagnetic coupling between qubit 210 and qubit 220) dominate. For further discussion of adiabatic couplings, see e.g., Hutter et al., arXiv:cond-mat/0602086 (2006).
The Hamiltonians which coupler 200 is capable of embedding allow for diagonalized ZZ coupling interactions (e.g., σz1σz2 interactions) and do not allow for the production of off-diagonal YY couplings (e.g., σy1σy1 interactions). The Hamiltonian H for coupler 200 is:
      H    =                            ∑                                    i              =              1                        ,            2                          ⁢                              h            i                    ⁢                      σ            z            i                              +                        J                      1            ,            2                    ZZ                ⁢                  σ          z          1                ⁢                  σ          z          2                      ,where 1 and 2 represent qubit 210 and qubit 220 respectively, h1 is the energy bias of qubit 210 and is controllable by adjusting the amount of flux 215 threading the loop 211, h2 is the energy bias of qubit 220 and is controllable by adjusting the amount of flux 225 threading the loop 221, σz1 is the z-Pauli matrix of qubit 210, σz2 is the z-Pauli matrix of qubit 220, and J1,2ZZ is the diagonal coupling coefficient between qubit 210 and qubit 220 and is controllable by adjusting the amount of flux 205 threading compound Josephson junction 202. The parameters Δ1 and Δ2 are the flux tunneling amplitude terms of qubit 210 and qubit 220 respectively. The transverse terms, Δ1 and Δ2, are respectively controllable by adjusting the amount of flux 213 threading compound Josephson junction 212 and the amount of flux 223 threading compound Josephson junction 222. Δ1 and Δ2 are suppressed during the operation of coupler 200 and effectively have a value of about zero and may therefore ignored within the Hamiltonian H of coupler 200.
For further discussion of persistent current couplers, see e.g., U.S. patent Ser. No. 12/017,995.